use std::mem::{size_of, align_of};
use std::slice;

/// 缓存行大小（假设为64字节，适用于大多数现代CPU）
const CACHE_LINE_SIZE: usize = 64;

/// 数据布局优化器
pub struct DataLayoutOptimizer;

impl DataLayoutOptimizer {
    /// 对齐到缓存行
    #[inline]
    pub fn cache_line_align(size: usize) -> usize {
        (size + CACHE_LINE_SIZE - 1) & !(CACHE_LINE_SIZE - 1)
    }
    
    /// 检查指针是否已对齐到缓存行
    #[inline]
    pub fn is_cache_line_aligned<T>(ptr: *const T) -> bool {
        (ptr as usize) % CACHE_LINE_SIZE == 0
    }
    
    /// 计算结构体中字段的缓存友好偏移量
    pub fn calculate_cache_friendly_offset(current_size: usize, field_size: usize, field_align: usize) -> usize {
        // 首先按照字段的对齐要求进行对齐
        let aligned_offset = (current_size + field_align - 1) & !(field_align - 1);
        
        // 检查是否会跨越缓存行边界
        let cache_line_start = aligned_offset / CACHE_LINE_SIZE;
        let cache_line_end = (aligned_offset + field_size - 1) / CACHE_LINE_SIZE;
        
        // 如果会跨越缓存行边界，则对齐到下一个缓存行
        if cache_line_start != cache_line_end {
            ((aligned_offset / CACHE_LINE_SIZE) + 1) * CACHE_LINE_SIZE
        } else {
            aligned_offset
        }
    }
}

/// 数组数据布局类型
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ArrayLayout {
    /// 行优先（C风格）
    RowMajor,
    /// 列优先（Fortran风格）
    ColumnMajor,
    /// 平铺（用于矩阵乘法等操作的优化）
    Tiled(usize),
}

/// 二维数组包装器，提供不同的数据布局
pub struct Array2D<T> {
    data: Vec<T>,
    rows: usize,
    cols: usize,
    layout: ArrayLayout,
    tile_size: usize,
}

impl<T: Clone + Default> Array2D<T> {
    /// 创建新的二维数组
    pub fn new(rows: usize, cols: usize, layout: ArrayLayout) -> Self {
        let tile_size = match layout {
            ArrayLayout::Tiled(size) => size,
            _ => 0,
        };
        
        let capacity = rows * cols;
        let mut data = Vec::with_capacity(capacity);
        data.resize(capacity, T::default());
        
        Array2D {
            data,
            rows,
            cols,
            layout,
            tile_size,
        }
    }
    
    /// 获取行数
    pub fn rows(&self) -> usize {
        self.rows
    }
    
    /// 获取列数
    pub fn cols(&self) -> usize {
        self.cols
    }
    
    /// 获取数据布局
    pub fn layout(&self) -> ArrayLayout {
        self.layout
    }
    
    /// 获取元素
    pub fn get(&self, row: usize, col: usize) -> Option<&T> {
        if row >= self.rows || col >= self.cols {
            return None;
        }
        
        let index = self.calculate_index(row, col);
        self.data.get(index)
    }
    
    /// 获取可变元素
    pub fn get_mut(&mut self, row: usize, col: usize) -> Option<&mut T> {
        if row >= self.rows || col >= self.cols {
            return None;
        }
        
        let index = self.calculate_index(row, col);
        self.data.get_mut(index)
    }
    
    /// 设置元素
    pub fn set(&mut self, row: usize, col: usize, value: T) -> Result<(), &'static str> {
        if row >= self.rows || col >= self.cols {
            return Err("Index out of bounds");
        }
        
        let index = self.calculate_index(row, col);
        self.data[index] = value;
        Ok(())
    }
    
    /// 获取行视图
    pub fn row(&self, row: usize) -> Option<Vec<&T>> {
        if row >= self.rows {
            return None;
        }
        
        let mut result = Vec::with_capacity(self.cols);
        for col in 0..self.cols {
            result.push(self.get(row, col).unwrap());
        }
        
        Some(result)
    }
    
    /// 获取列视图
    pub fn col(&self, col: usize) -> Option<Vec<&T>> {
        if col >= self.cols {
            return None;
        }
        
        let mut result = Vec::with_capacity(self.rows);
        for row in 0..self.rows {
            result.push(self.get(row, col).unwrap());
        }
        
        Some(result)
    }
    
    /// 获取原始数据
    pub fn data(&self) -> &[T] {
        &self.data
    }
    
    /// 获取可变原始数据
    pub fn data_mut(&mut self) -> &mut [T] {
        &mut self.data
    }
    
    /// 计算索引
    fn calculate_index(&self, row: usize, col: usize) -> usize {
        match self.layout {
            ArrayLayout::RowMajor => {
                row * self.cols + col
            }
            ArrayLayout::ColumnMajor => {
                col * self.rows + row
            }
            ArrayLayout::Tiled(_) => {
                let tile_row = row / self.tile_size;
                let tile_col = col / self.tile_size;
                let local_row = row % self.tile_size;
                let local_col = col % self.tile_size;
                
                let tiles_per_row = (self.cols + self.tile_size - 1) / self.tile_size;
                let tile_index = tile_row * tiles_per_row + tile_col;
                let local_index = local_row * self.tile_size + local_col;
                
                tile_index * (self.tile_size * self.tile_size) + local_index
            }
        }
    }
}

/// 结构体字段布局优化器
pub struct StructLayoutOptimizer;

impl StructLayoutOptimizer {
    /// 对字段进行排序以优化内存布局
    pub fn optimize_field_order<T>(fields: &mut [(T, usize, usize)]) {
        // 按大小降序排序，这样大字段会先放置，减少填充
        fields.sort_by(|a, b| b.1.cmp(&a.1));
    }
    
    /// 计算结构体的最佳大小和对齐
    pub fn calculate_optimal_layout(fields: &[(usize, usize)]) -> (usize, usize) {
        if fields.is_empty() {
            return (0, 1);
        }
        
        let mut size = 0;
        let mut align = 1;
        
        for &(field_size, field_align) in fields {
            // 更新结构体的对齐要求
            align = align.max(field_align);
            
            // 计算字段的偏移量
            size = DataLayoutOptimizer::calculate_cache_friendly_offset(size, field_size, field_align);
            size += field_size;
        }
        
        // 最终大小需要按结构体的对齐要求对齐
        size = (size + align - 1) & !(align - 1);
        
        (size, align)
    }
}

/// 向量化友好的数据结构
pub struct SoA<T> {
    data: Vec<Vec<T>>,
    len: usize,
}

impl<T: Clone + Default> SoA<T> {
    /// 创建新的SoA结构
    pub fn new(components: usize, capacity: usize) -> Self {
        let mut data = Vec::with_capacity(components);
        for _ in 0..components {
            let mut component = Vec::with_capacity(capacity);
            component.resize(capacity, T::default());
            data.push(component);
        }
        
        SoA {
            data,
            len: 0,
        }
    }
    
    /// 添加元素
    pub fn push(&mut self, values: &[T]) -> Result<(), &'static str> {
        if values.len() != self.data.len() {
            return Err("Component count mismatch");
        }
        
        if self.len >= self.data[0].capacity() {
            // 需要扩容
            let new_capacity = self.data[0].capacity() * 2;
            for component in &mut self.data {
                component.reserve(new_capacity - component.capacity());
            }
        }
        
        for (i, value) in values.iter().enumerate() {
            self.data[i].push(value.clone());
        }
        
        self.len += 1;
        Ok(())
    }
    
    /// 获取元素
    pub fn get(&self, component: usize, index: usize) -> Option<&T> {
        self.data.get(component)?.get(index)
    }
    
    /// 获取可变元素
    pub fn get_mut(&mut self, component: usize, index: usize) -> Option<&mut T> {
        self.data.get_mut(component)?.get_mut(index)
    }
    
    /// 获取组件
    pub fn component(&self, component: usize) -> Option<&[T]> {
        self.data.get(component).map(|v| &v[..self.len])
    }
    
    /// 获取可变组件
    pub fn component_mut(&mut self, component: usize) -> Option<&mut [T]> {
        self.data.get_mut(component).map(|v| &mut v[..self.len])
    }
    
    /// 获取长度
    pub fn len(&self) -> usize {
        self.len
    }
    
    /// 检查是否为空
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }
    
    /// 获取组件数量
    pub fn component_count(&self) -> usize {
        self.data.len()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    
    #[test]
    fn test_cache_line_align() {
        assert_eq!(DataLayoutOptimizer::cache_line_align(1), 64);
        assert_eq!(DataLayoutOptimizer::cache_line_align(64), 64);
        assert_eq!(DataLayoutOptimizer::cache_line_align(65), 128);
    }
    
    #[test]
    fn test_array2d_row_major() {
        let mut arr = Array2D::new(3, 4, ArrayLayout::RowMajor);
        
        // 设置元素
        for i in 0..3 {
            for j in 0..4 {
                arr.set(i, j, i * 10 + j).unwrap();
            }
        }
        
        // 验证元素
        for i in 0..3 {
            for j in 0..4 {
                assert_eq!(*arr.get(i, j).unwrap(), i * 10 + j);
            }
        }
        
        // 验证行视图
        let row = arr.row(1).unwrap();
        assert_eq!(row.len(), 4);
        assert_eq!(*row[0], 10);
        assert_eq!(*row[1], 11);
        assert_eq!(*row[2], 12);
        assert_eq!(*row[3], 13);
        
        // 验证列视图
        let col = arr.col(2).unwrap();
        assert_eq!(col.len(), 3);
        assert_eq!(*col[0], 2);
        assert_eq!(*col[1], 12);
        assert_eq!(*col[2], 22);
    }
    
    #[test]
    fn test_array2d_column_major() {
        let mut arr = Array2D::new(3, 4, ArrayLayout::ColumnMajor);
        
        // 设置元素
        for i in 0..3 {
            for j in 0..4 {
                arr.set(i, j, i * 10 + j).unwrap();
            }
        }
        
        // 验证元素
        for i in 0..3 {
            for j in 0..4 {
                assert_eq!(*arr.get(i, j).unwrap(), i * 10 + j);
            }
        }
    }
    
    #[test]
    fn test_array2d_tiled() {
        let mut arr = Array2D::new(4, 4, ArrayLayout::Tiled(2));
        
        // 设置元素
        for i in 0..4 {
            for j in 0..4 {
                arr.set(i, j, i * 10 + j).unwrap();
            }
        }
        
        // 验证元素
        for i in 0..4 {
            for j in 0..4 {
                assert_eq!(*arr.get(i, j).unwrap(), i * 10 + j);
            }
        }
    }
    
    #[test]
    fn test_struct_layout_optimizer() {
        // 模拟一些字段
        let mut fields = vec![
            ("field1", 4, 4),  // (name, size, align)
            ("field2", 8, 8),
            ("field3", 1, 1),
            ("field4", 2, 2),
        ];
        
        // 优化字段顺序
        StructLayoutOptimizer::optimize_field_order(&mut fields);
        
        // 验证优化结果（应该按大小降序排列）
        assert_eq!(fields[0].0, "field2");
        assert_eq!(fields[1].0, "field1");
        assert_eq!(fields[2].0, "field4");
        assert_eq!(fields[3].0, "field3");
        
        // 计算最佳布局
        let field_specs = fields.iter().map(|&(_, size, align)| (size, align)).collect::<Vec<_>>();
        let (size, align) = StructLayoutOptimizer::calculate_optimal_layout(&field_specs);
        
        // 验证结果
        assert!(size >= 15); // 至少需要15字节
        assert_eq!(align, 8); // 最大对齐要求是8
    }
    
    #[test]
    fn test_soa() {
        let mut soa = SoA::new(3, 10);
        
        // 添加元素
        soa.push(&[1, 2, 3]).unwrap();
        soa.push(&[4, 5, 6]).unwrap();
        soa.push(&[7, 8, 9]).unwrap();
        
        // 验证元素
        assert_eq!(*soa.get(0, 0).unwrap(), 1);
        assert_eq!(*soa.get(1, 0).unwrap(), 2);
        assert_eq!(*soa.get(2, 0).unwrap(), 3);
        
        assert_eq!(*soa.get(0, 1).unwrap(), 4);
        assert_eq!(*soa.get(1, 1).unwrap(), 5);
        assert_eq!(*soa.get(2, 1).unwrap(), 6);
        
        // 验证组件
        let comp0 = soa.component(0).unwrap();
        assert_eq!(comp0, &[1, 4, 7]);
        
        let comp1 = soa.component(1).unwrap();
        assert_eq!(comp1, &[2, 5, 8]);
        
        // 修改元素
        *soa.get_mut(0, 0).unwrap() = 10;
        assert_eq!(*soa.get(0, 0).unwrap(), 10);
        
        // 修改组件
        let comp0_mut = soa.component_mut(0).unwrap();
        comp0_mut[1] = 40;
        assert_eq!(*soa.get(0, 1).unwrap(), 40);
    }
}